from random import randint


def findKthMax(l, k):
    if k > len(l):
        return
    key = randint(0, len(l) - 1)
    keyv = l[key]
    sl = [i for i in l[:key] + l[key + 1:] if i < keyv]
    bl = [i for i in l[:key] + l[key + 1:] if i >= keyv]
    if len(bl) == k - 1:
        return keyv
    elif len(bl) >= k:
        return findKthMax(bl, k)
    else:
        return findKthMax(sl, k - len(bl) - 1)


if __name__ == '__main__':
    a = [2, 4, 6, 8, 9, 10]
    b = [0, 1, 3, 6, 7, 9, 100, 134]
    counta = 0
    countb = 0

    c = []
    for i in range(counta, len(a)):
        for j in range(countb, len(b)):
            if b[j] <= a[i]:
                c.append(b[j])
                countb += 1
            else:
                c.append(a[i])
                counta += 1
                break

    if counta < len(a):
        for i in range(counta, len(a)):
            c.append(a[i])
    if countb < len(b):
        for j in range(countb, len(b)):
            c.append(b[j])

    print(findKthMax(c, 2))
